BinaryTree.java

packagesection24_BinaryTree;

importjava.util.Scanner;
importjava.util.Stack;

publicclassBinaryTree {

Scannersc = newScanner(System.in);

privateclassNode {
intdata;
Nodeleft;
Noderight;
 }

privateNoderoot;

publicBinaryTree() {
this.root = takeInput(null, false);
 }

// parameterized constructor for tree construction using preorder and
// inorder traversal
publicBinaryTree(int[] inTraverse, int[] preTraverse) {

intinStartIdx = 0, inEndIdx = inTraverse.length - 1;
intpreStartIdx = 0, preEndIdx = preTraverse.length - 1;

this.root = construct(preTraverse, preStartIdx, preEndIdx, inTraverse, inStartIdx, inEndIdx);
 }

privateNodetakeInput(Nodeparent, booleanisLeftChild) {

// prompt
if (parent == null) {
System.out.println("Enter the data for root node: ");
 } else {
if (isLeftChild)
System.out.println("Enter the data for left child of " + parent.data);
else
System.out.println("Enter the data for right child of " + parent.data);
 }

// take input of data
intitem = sc.nextInt();
// create new Node
NodenewNode = newNode();
newNode.data = item;

System.out.println("Do you have left child of " + newNode.data + " ?, press Y/N");
charhasLeft = sc.next().charAt(0);

// if left child exists, create it
if (hasLeft == 'Y') {
newNode.left = takeInput(newNode, true);
 }

System.out.println("Do you have right child of " + newNode.data + " ?, press Y/N");
charhasRight = sc.next().charAt(0);

// if right child exists, create it
if (hasRight == 'Y') {
newNode.right = takeInput(newNode, false);
 }

// node is ready
returnnewNode;
 }

// O(N)Time
publicvoiddisplay() {
System.out.println("\n--------------------");
display(root);
System.out.println("--------------------");
 }

privatevoiddisplay(Nodenode) {
// base case
if (node == null)
return;

// self-work
Stringstr = "";

if (node.left != null)
str += node.left.data;
else
str += ". ";

str += " => " + node.data + " <= ";

if (node.right != null)
str += node.right.data;
else
str += '.';

System.out.println(str);

// smaller problems
display(node.left);
display(node.right);
 }

// O(N)Time
publicintsize() {
returnsize(root);
 }

privateintsize(Nodenode) {
if (node == null)
return0;

intlsize = size(node.left);
intrsize = size(node.right);

returnlsize + rsize + 1;
 }

// O(N)Time
publicintmax() {
returnmax(root);
 }

/*
 * private int max(Node node) {
 * 
 * int totalMax = node.data;
 * 
 * if (node.left != null) { int lmax = max(node.left);
 * 
 * if (lmax > totalMax) totalMax = lmax; }
 * 
 * if (node.right != null) { int rmax = max(node.right);
 * 
 * if (rmax > totalMax) totalMax = rmax; }
 * 
 * return totalMax; }
 */

// clean code to find max
privateintmax(Nodenode) {
if (node == null)
returnInteger.MIN_VALUE;

intlmax = max(node.left);
intrmax = max(node.right);

returnMath.max(node.data, Math.max(lmax, rmax));
 }

// O(N)Time
publicbooleanfind(intitem) {
returnfind(root, item);
 }

privatebooleanfind(Nodenode, intitem) {
if (node == null)
returnfalse;

if (node.data == item)
returntrue;

booleanlResult = find(node.left, item);
if (lResult)
returntrue;

booleanrResult = find(node.right, item);
if (rResult)
returntrue;

returnfalse;
 }

// O(N)Time
publicintheight() {
returnheight(root);
 }

privateintheight(Nodenode) {
if (node == null)
return -1;

intlheight = height(node.left);
intrheight = height(node.right);

returnMath.max(lheight, rheight) + 1; // self-work
 }

// approach 1 - using global variable
privateintdiameterAns = Integer.MIN_VALUE;

publicintdiameter() {
diameter(root);
returndiameterAns;
 }

privatevoiddiameter(Nodenode) {

if (node == null) {
return;
 }

intpresentNodeRoot = height(node.left) + height(node.right) + 2;

if (presentNodeRoot > diameterAns) {
diameterAns = presentNodeRoot;
 }

diameter(node.left);
diameter(node.right);
 }

// approach 2
// O(N^2)Time
publicintdiameter2() {
returndiameter2(root);
 }

privateintdiameter2(Nodenode) {

if (node == null)
return0;

// max distance between 2 leaf nodes might lie in left subtree,
// factor1: left diameter
intlDiameter = diameter2(node.left);

// max distance between 2 leaf nodes might lie in right subtree,
// factor2: right diameter
intrDiameter = diameter2(node.right);

// self node might be the root node of diameter, factor3: self diameter
introotDiameter = height(node.left) + height(node.right) + 2;

returnMath.max(rootDiameter, Math.max(lDiameter, rDiameter));
 }

privateclassDiaPair {
intpairDiameter = 0;
intpairHeight = -1;
 }

publicintdiameter3() {
DiaPairansPair = diameter3(root);
returnansPair.pairDiameter;
 }

privateDiaPairdiameter3(Nodenode) {

if (node == null) {
returnnewDiaPair();
 }

DiaPairleftDiaPair = diameter3(node.left);
DiaPairrightDiaPair = diameter3(node.right);

DiaPairselfDiaPair = newDiaPair();

intlDiameter = leftDiaPair.pairDiameter;
intrDiameter = rightDiaPair.pairDiameter;
intselfDiameter = leftDiaPair.pairHeight + rightDiaPair.pairHeight + 2;

selfDiaPair.pairDiameter = Math.max(selfDiameter, Math.max(lDiameter, rDiameter));
selfDiaPair.pairHeight = Math.max(leftDiaPair.pairHeight, rightDiaPair.pairHeight) + 1;

returnselfDiaPair;
 }

// O(N^2) Time
publicbooleanisBalanced() {
returnisBalanced(root);
 }

privatebooleanisBalanced(Nodenode) {

if (node == null) {
returntrue;
 }

booleanleftBalanced = isBalanced(node.left);
booleanrightBalanced = isBalanced(node.right);

// for root node of current subtree
intbalancingFactor = height(node.left) - height(node.right);

if (leftBalanced && rightBalanced && balancingFactor >= -1 && balancingFactor <= 1) {
returntrue;
 } else {
returnfalse;
 }
 }

// Efficient approach to check if binary tree is Balanced

privateclassBalPair {
booleanisBal = true;
intht = -1;
 }

// O(N) Time
publicbooleanisBalanced3() {
BalPairans = isBalanced3(root);
returnans.isBal;
 }

privateBalPairisBalanced3(Nodenode) {

if (node == null) {
returnnewBalPair();
 }

BalPairleftBalPair = isBalanced3(node.left);
BalPairrightBalPair = isBalanced3(node.right);

BalPairselfBalPair = newBalPair();

// logic from first approach
booleanleftBalanced = leftBalPair.isBal;
booleanrightBalanced = rightBalPair.isBal;
intbalancingFactor = leftBalPair.ht - rightBalPair.ht;

if (leftBalanced && rightBalanced && balancingFactor >= -1 && balancingFactor <= 1) {
selfBalPair.isBal = true;
 } else {
selfBalPair.isBal = false;
 }

selfBalPair.ht = Math.max(leftBalPair.ht, rightBalPair.ht) + 1;

returnselfBalPair;
 }

// Binary Tree Traversals

publicvoidpreorder() {
preorder(root);
 }

privatevoidpreorder(Nodenode) {
if (node == null)
return;

// NLR - Node, Left, Right
System.out.print(node.data + " ");
preorder(node.left);
preorder(node.right);
 }

publicvoidinorder() {
inorder(root);
 }

privatevoidinorder(Nodenode) {
if (node == null)
return;

// LNR, Left, Node, Right
inorder(node.left);
System.out.print(node.data + " ");
inorder(node.right);
 }

publicvoidpostorder() {
postorder(root);
 }

privatevoidpostorder(Nodenode) {
if (node == null)
return;

// LRN, Left, Right, Node
postorder(node.left);
postorder(node.right);
System.out.print(node.data + " ");
 }

// pre-order traversal using Iterative approach
privateclassPair {
Nodenode;
booleanselfDone; // Node traversed
booleanleftDone; // Left traversed
booleanrightDone; // Right traversed
 }

publicvoidpreorderIterative() {

// create a Stack
Stack<Pair> stack = newStack<>();

// create starting pair
PairstartPair = newPair();
startPair.node = root;

// put starting pair in Stack
stack.push(startPair);

while (!stack.isEmpty()) {

PairtopmostPair = stack.peek();

if (topmostPair.node == null) {
stack.pop();
continue;
 }

if (topmostPair.selfDone == false) {
System.out.print(topmostPair.node.data + " "); // N
topmostPair.selfDone = true;

 } elseif (topmostPair.leftDone == false) {

// create a new pair
PairnewLPair = newPair();
newLPair.node = topmostPair.node.left; // L

// if (newLPair.node != null)
stack.push(newLPair);

topmostPair.leftDone = true;

 } elseif (topmostPair.rightDone == false) {

PairnewRPair = newPair();
newRPair.node = topmostPair.node.right; // R

// if (newRPair.node != null)
stack.push(newRPair);

topmostPair.rightDone = true;
 } else {
stack.pop();
 }
 }
 }

publicintsum() {
returnsum(root);
 }

privateintsum(Nodenode) {

if (node == null) {
return0;
 }

intleftSum = sum(node.left);
intrightSum = sum(node.right);

returnleftSum + rightSum + node.data;
 }

// maximum subtree sum

// approach 1 - using global variable
/*
 * private int maxSubsumAns = Integer.MIN_VALUE;
 * 
 * public int maxSubtreeSum1() { maxSubtreeSum1(root); return maxSubsumAns;
 * }
 * 
 * private void maxSubtreeSum1(Node node) {
 * 
 * if (node == null) return;
 * 
 * int lsum = sum(node.left); if (lsum > maxSubsumAns) { maxSubsumAns =
 * lsum; } maxSubtreeSum1(node.left);
 * 
 * int rsum = sum(node.right); if (rsum > maxSubsumAns) { maxSubsumAns =
 * rsum; } maxSubtreeSum1(node.right);
 * 
 * int currentSubtreesum = lsum + rsum + node.data;
 * 
 * if (currentSubtreesum > maxSubsumAns) { maxSubsumAns = currentSubtreesum;
 * } }
 */

// clean code of maxSubtreeSum1()
privateintmaxSubsumAns2 = Integer.MIN_VALUE;

publicintmaxSubtreeSum1() {
maxSubtreeSum1(root);
returnmaxSubsumAns2;
 }

privateintmaxSubtreeSum1(Nodenode) {

if (node == null)
return0;

intlsum = maxSubtreeSum1(node.left);
intrsum = maxSubtreeSum1(node.right);

intnodeans = lsum + rsum + node.data;

if (nodeans > maxSubsumAns2) {
maxSubsumAns2 = nodeans;
 }

returnnodeans;
 }

// O(N^2) Time
publicintmaxSubtreeSum2() {
returnmaxSubtreeSum2(root);
 }

// recursion returns maximum subtree sum
privateintmaxSubtreeSum2(Nodenode) {

if (node == null)
returnInteger.MIN_VALUE; // not zero, because node data can be
// negative & we are finding Max value

intlMaxSubtreeSum = maxSubtreeSum2(node.left);
intrMaxSubtreeSum = maxSubtreeSum2(node.right);

// current node sum + entire left subtree sum + entire right subtree sum
// int selfSum = node.data + sum(node.left) + sum(node.right);
intselfSum = sum(node);

intans = Math.max(selfSum, Math.max(lMaxSubtreeSum, rMaxSubtreeSum));

returnans;
 }

// approach 3

privateclassMaxSubtreeSumPair {
intentireSum = 0;
intmaxSubtreeSum = Integer.MIN_VALUE;
 }

// O(N) Time
publicintmaxSubtreeSum3() {
returnmaxSubtreeSum3(root).maxSubtreeSum;
 }

privateMaxSubtreeSumPairmaxSubtreeSum3(Nodenode) {

if (node == null) {
returnnewMaxSubtreeSumPair();
 }

MaxSubtreeSumPairlp = maxSubtreeSum3(node.left);
MaxSubtreeSumPairrp = maxSubtreeSum3(node.right);

MaxSubtreeSumPairselfpair = newMaxSubtreeSumPair();

selfpair.entireSum = lp.entireSum + rp.entireSum + node.data;
selfpair.maxSubtreeSum = Math.max(selfpair.entireSum, Math.max(lp.maxSubtreeSum, rp.maxSubtreeSum));

returnselfpair;
 }

publicNodeconstruct(int[] pre, intplow, intphigh, int[] in, intilow, intihigh) {

if (plow > phigh || ilow > ihigh) {
returnnull;
 }

// create a new node with plow
NodenewNode = newNode();
newNode.data = pre[plow]; // root node initially

// search for pre[plow] in inorder array
intsearchIdx = -1;
intnumElements = 0;
for (inti = ilow; i <= ihigh; i++) {
if (pre[plow] == in[i]) {
searchIdx = i;
break;
 }
numElements++;
 }

// left and right child call
newNode.left = construct(pre, plow + 1, plow + numElements, in, ilow, searchIdx - 1);
newNode.right = construct(pre, plow + numElements + 1, phigh, in, searchIdx + 1, ihigh);

returnnewNode;
 }

publicbooleanflipEquivalent(BinaryTreeother) {
returnflipEquivalent(this.root, other.root);
 }

privatebooleanflipEquivalent(Nodenode1, Nodenode2) {

// if both nodes are null, they are flip equivalent
if (node1 == null && node2 == null) {
returntrue;
 }
// if either of node is null, they are not flip equivalent
if (node1 == null || node2 == null) {
returnfalse;
 }

if (node1.data != node2.data) {
returnfalse;
 }
// case 1 - node is not flipped

// left subtree of node1 & left subtree of node2
booleanleftleft = flipEquivalent(node1.left, node2.left);
// right subtree of node1 & right subtree of node2
booleanrightright = flipEquivalent(node1.right, node2.right);

if (leftleft && rightright)
returntrue;

// case 2 - node is flipped

// left subtree of node1 & right subtree of node2
booleanleftright = flipEquivalent(node1.left, node2.right);
// right subtree of node1 & left subtree of node2
booleanrightleft = flipEquivalent(node1.right, node2.left);

return (leftleft && rightright) || (leftright && rightleft);
 }
}